//
// Created by wdq on 2022/9/8.
//
//
// Created by wdq on 2022/9/8.
//
#include <iostream>
template<typename ElemType>
struct ListNode {
    ElemType value;
    ListNode *next;

    /*!
     * 递归释放空间
     */

    void print() {
        std::cout << value << std::endl;
    }


    ListNode() : value(), next(nullptr) {}


    explicit ListNode(ElemType value) : value(value), next(nullptr) {}

    ListNode(ElemType value, ListNode *next) : value(value), next(next) {}

    ~ListNode() {
        delete next;
    }
};

template<typename ElemType>
struct LinkList {
    ListNode<ElemType> *header;
    int length;

    LinkList() {
        this->header = new ListNode<ElemType>();
        this->length = 0;
    }

    ~LinkList() {
        delete header;
    }

    void insertByHead(ElemType value) {
        ListNode<ElemType> *p = header->next;
        header->next = new ListNode<ElemType>(value, p);
        length++;

    }

    void insertByTail(ElemType value) {
        auto p = header;
        for (; p->next != nullptr; p = p->next);
        p->next = new ListNode<ElemType>(value);
        this->length++;

    }

    ListNode<ElemType> *get(int index) {
        if (index < 0 && index >= this->length) {
            throw std::out_of_range("the index is not legal");
        }
        auto p = header->next;
        for (; p != nullptr && index > 0; p = p->next, index--);
        return p;
    }

    void set(int index, ElemType value) {
        auto p = get(index);
        p->value = value;
    }

    ListNode<ElemType> *find(ElemType value) {
        auto p = header->next;
        for (; p != nullptr; p = p->next) {
            if (p->value == value) {
                break;
            }
        }
        return p;

    }

    void deleteAfter(ListNode<ElemType> *p) {
        if (p == nullptr) {
            return;
        }
        auto q = p->next;
        if (q == nullptr) {
            return;
        }
        p->next = q->next;
        q->next = nullptr;
        delete q;
        this->length--;
    }

    void print() {
        std::cout << "header -> ";
        for (auto p = header->next; p != nullptr; p = p->next) {
            std::cout << p->value << " -> ";
        }
        std::cout << "^" << std::endl;
    }
};

template<typename ElemType>
struct Queue : public LinkList<ElemType> {
    ListNode<ElemType> *tail;

    Queue() : LinkList<ElemType>() {
        this->tail = this->header;
    }

    void enqueue(ElemType value) {
        tail->next = new ListNode<ElemType>(value);
        tail = tail->next;
        this->length++;

    }

    ElemType dequeue() {
        if (isEmpty()) {
            throw std::out_of_range("the queue is empty!");
        }
        auto item = this->header->next->value;
        if (this->length == 1) {
            this->tail = this->header;
        }
        LinkList<ElemType>::deleteAfter(this->header);
        return item;

    }

    bool isEmpty() {
        return this->header->next == nullptr;
    }
};

int main() {
    Queue<int> queue;
    for (int i = 0; i <= 5; i++) {
        queue.enqueue(i);
    }
    while (!queue.isEmpty()) {
        queue.print();
        queue.dequeue();
    }
    queue.print();

}
/*
  ___________.__                   __               _____                 _____  .__      ._.
  \__    ___/|  |__ _____    ____ |  | __  ______ _/ ____\___________    /     \ |__| ____| |
    |    |   |  |  \\__  \  /    \|  |/ / /  ___/ \   __\/  _ \_  __ \  /  \ /  \|  |/    \ |
    |    |   |   Y  \/ __ \|   |  \    <  \___ \   |  | (  <_> )  | \/ /    Y    \  |   |  \|
    |____|   |___|  (____  /___|  /__|_ \/____  >  |__|  \____/|__|    \____|__  /__|___|  /_
                  \/     \/     \/     \/     \/                               \/        \/\/
*/